#include <iostream>

using namespace::std;

void print_array(int *a, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}


int partition(int *a, int l, int r)
{
    int pivort = l;
    int index = pivort;
    int pivot_value = a[pivort];
    swap(a[pivort], a[r]);
    for(int i = l; i < r; i++)
    {
        if(pivot_value > a[i])
        {
            cout << "swap index:" << index << " and:" << i << endl;
            swap(a[index++], a[i]);
        }
    }
    swap(a[index], a[r]);
    return index;
}

void quick_sort(int *a, int l, int r)
{
    int pivort = 0;
    if(l < r)
    {
        pivort = partition(a, l, r);
        quick_sort(a, l, pivort - 1);
        quick_sort(a, pivort + 1, r);
    }
}

int main(int argc, char** argv)
{
    int array[10] = {3, 4, 6, 3, 8, -4, 14, 40, 9, 10};
    int size = sizeof(array)/sizeof(array[0]);
    
    print_array(array, size);
    quick_sort(array, 0, size - 1);
    print_array(array, size);
}


